package com.icehand.learning.matcher.boyermoore;

import com.icehand.learning.matcher.Matcher;

/**
 * Boyer-Moore搜索算法
 * 坏字符规则：后移位数 = 坏字符串的位置 - 搜索词中上一次出现的位置（如果坏字符串不包含在搜素词中，则上一次的位置为-1）
 * 好后缀规则：后移位数 = 好后缀的位置 - 搜索词中的上一次出现的位置
 * 后移的位数 = Max(坏字符规则位数 , 好后缀规则位数)
 * Created by icehand on 2017/5/3.
 */
public class BoyerMoore implements Matcher{
	private static final int ALPHABET_SIZE = Character.MAX_VALUE+1;

	private String text;
	private String pattern;

	private int[] last;
	private int[] match;
	private int[] suffix;

	public BoyerMoore(String text ,String pattern){
		this.text = text;
		this.pattern = pattern;
		last = new int[ALPHABET_SIZE];
		match = new int[pattern.length()];
		suffix = new int[pattern.length()];
	}

	/**
	 * 搜索，存在返回首次出现的位置，否则返回-1
	 * @return int
	 */
	public int match(){
		//预处理
		computeLast();//坏字符串
		computeMatch();//好后缀

		//搜索
		int i = pattern.length()-1;//text的位置
		int j = pattern.length()-1;//pattern的位置
		while (i < text.length()) {
			//如果匹配,就从后至前进行匹配
			if (pattern.charAt(j) == text.charAt(i)) {
				if (j == 0) {
					//第0位pattern与text也匹配，即找到
					return i;
				}
				j--;
				i--;
			} else {
				i += pattern.length()- 1 - j + Math.max(j - last[text.charAt(i)], match[j]);//根据坏字符串规则和好后缀规则，取text后移的位数
				j = pattern.length() - 1;//pattern从最后开始
			}
		}

		return -1;
	}

	public boolean contains(){
		return match()!=-1;
	}

	/**
	 * 计算坏字符数组
	 * last[]的下标为字符，数组存储着 pattern中字符最后出现的位置，如果字符不存在于pattern，那么那个位置的值为-1
	 */
	private void computeLast(){
		for (int k = 0 ; k < last.length ; k++){
			last[k] = -1;
		}

		for (int j = pattern.length()-1 ; j >= 0; j--) {
			if(last[pattern.charAt(j)] < 0){
				last[pattern.charAt(j)] = j;
			}
		}
	}

	/**
	 * 计算好后缀数组
	 * match[]的下标为数字
	 * 分为三种情况考虑：
	 *  1、模式串中有子串和好后缀完全匹配，则将最靠右的那个子串移动到好后缀的位置继续进行匹配
	 *  2、如果不存在和好后缀完全匹配的子串，则在好后缀中找到具有如下特征的最长子串，使得P[m-s...m] = P[0...s]
	 *  3、如果完全不存在和好后缀匹配的子串，则右移整个模式串
	 */
	private void computeMatch(){
		for(int j = 0 ;j<match.length ; j++){
			match[j] = match.length;
		}

		computeSuffix();

		for(int i=suffix.length-1;i>=0;i--){
			if(i+1==suffix[i]){
				for(int j=0;j<suffix.length-1-i;j++)
				{
					if(suffix.length==match[j]){
						match[j]=suffix.length-1-i;
					}
				}
			}
		}

		for(int i=0;i<=suffix.length-2;i++){
			match[suffix.length-1-suffix[i]]=suffix.length-1-i;
		}
	}

	private void computeSuffix(){
		int f=suffix.length-2;
		suffix[suffix.length-1]=suffix.length;
		int g=suffix.length-1;
		for(int i=suffix.length-2;i>=0;--i){
			if(i>g&&suffix[i+suffix.length-1-f]<i-g)
			{
				suffix[i]=suffix[i+suffix.length-1-f];
			}
			else
			{
				if(i<g)
				{
					g=i;
				}
				f=i;
				while(g>=0&&pattern.charAt(g)==pattern.charAt(g+pattern.length()-1-f)){
					--g;
				}
				suffix[i]=f-g;
			}
		}
	}
}
